package com.lisp.algorithm.sort;

import com.lisp.algorithm.util.SortUtil;

public class HeapSort {

    public static void main(String[] args) {
        SortUtil.test(HeapSort::heapSort);
    }
    
    public static void heapSort(int a[]) {
        buildMaxHeap(a);
        for(int heapSize=a.length-1; heapSize>0; heapSize--) {
            swap(a, 0, heapSize);
            maxHeapify(a, 0, heapSize);
        }
    }
    
    public static void buildMaxHeap(int a[]) {
        for(int i=(a.length-1)/2; i>=0; i--) {
            maxHeapify(a, i, a.length);
        }
    }
    
    public static void maxHeapify(int a[], int i, int heapSize) {
        int largestValueIndex = i;
        int largestValue = a[i];
        
        int leftChildIndex = 2*i + 1;
        if(leftChildIndex < heapSize && a[leftChildIndex] > largestValue) {
            largestValue = a[leftChildIndex];
            largestValueIndex = leftChildIndex;
        }
        
        int rightChildIndex = 2*i+2;
        if(rightChildIndex < heapSize && a[rightChildIndex] > largestValue) {
            largestValueIndex = rightChildIndex;
        }
        
        if(largestValueIndex != i) {
            swap(a, i, largestValueIndex);            
            maxHeapify(a, largestValueIndex, heapSize);
        }
    }
    
    static void swap(int a[], int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}
